Computer networks are a principal means of exchanging or transferring information (e.g. data, voice, text, video, etc.) among host machines connected to the network. The network comprises nodes connected, to each other and to the hosts, by links. Typically, each link is bidirectional, i.e. information may be conveyed in forward and reverse directions, and each link is characterized by a bandwidth capacity in each direction.
An important consideration in network operation is how the information is routed. When information is to be exchanged between two particular hosts, a bidirectional path is established in the network between them. Typically, this path that is established is a so-called "virtual circuit" (VC), by which it is meant that a host simply specifies the destination for the information, and the network delivers the information as though a circuit is connected to the destination. One of many different routes and techniques could be selected to deliver the information, but the particular selection is of no concern to the host. The task of routing is to select the nodes and links between the nodes that comprise the path taken by the VC so as to efficiently utilize network resources, e.g. route as many VCs as possible without exceeding the bandwidth capacity of any particular link. This is often achieved by selecting a path so as to minimize some cost function that reflects the amount of network resources, e.g. bandwidth of links in the path, required by the selected path. Although a variety of cost functions can be used, cost functions typically take into account the current network state (i.e., the network topology and current allocation and availability of network resources), delay through the network, etc. The routing problem is often further complicated in that the routing must be effectuated "online," i.e. without knowledge of what future routing demands will have on network resources. Although this problem may be solved by so-called "dynamic-rerouting" techniques, these techniques typically adversely affect the quality of service offered to users of the network.
The manner in which the routing problem for virtual circuits is addressed typically is based on whether the VCs are permanent or switched and on whether the routing is done with incomplete or complete information. Permanent VCs are paths for information transfer between hosts designed to operate and remain established for long periods of time, perhaps on the order of years. Switched VCs are designed to operate for hours or days, and thus networks of switched VCs are reconfigured more often. See, B. Awerbuch et al., "Throughput-Competitive On-line Routing," 34th Annual Symp. on Foundations of Comp. Sci., Palo Alto, Calif., November 1993. Routing with incomplete information means simply that the state of the network is not known or, if the state is known, that the state information is dated, e.g., that the available state information does not incorporate information regarding network resources allocated to the most recently routed VCs. Conversely, routing with complete information means that the state information is fully known and that the state information is up-to-date.
Previous techniques for routing permanent VCs have employed minimum hop routing in which the path going through the shortest number of nodes is selected. Recently, another method, employing exponential cost functions and scaling, has been suggested. See, J. Aspnes et al., "On-Line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing," Proc. 23rd Annual Syrup. on Theory of Computing, San Diego, Calif. , May 1993. In the scaling technique, a portion .gamma. of the bandwidth capacity of each link is initially apportioned, and a cost function is computed for routing a path given that apportioned bandwidth. When routing can no longer be achieved in the network with that apportioned bandwidth, more bandwidth can be apportioned, i.e. the scale factor .gamma. is increased. Typically, the function for determining the cost for a given link in a path for the requested VC is C.sub.l (x,.DELTA.x)=a.sup..gamma.x.sbsp.l.sup.+.gamma..DELTA.x.sbsp.l -a.sup..gamma.x.sbsp.l where C.sub.l (x,.DELTA.x) is the cost for link l in the path, a is a constant, x.sub.l is the fraction of the bandwidth capacity of the link that is in use and .DELTA.x.sub.l is the fraction of the bandwidth capacity of the link that is requested by the VC. Note that this is an exponential function in that the constant a is raised to a power--the power being a function of .gamma. and .DELTA.x.sub.l and of .gamma. and x.sub.l. Thus, the cost function includes a term in which the network resource (i.e. bandwidth) is in scaled form in the exponent of the term.
These prior techniques of permanent VC routing have shortcomings. For example, minimum hop techniques do not adequately reflect the current state of the network in path selection. Additionally, the scaling method, by restricting itself to a fraction of the total link bandwidth capacity, may select costly paths even when demand for VCs is low.